234. 回文链表

Similar Question

leading to the advanced question

Solution Tips

方案一: 快慢指针 + 翻转链表 + 回文判断

经典回文判断:

1. 翻转之后是否一样
2. 从中间开始遍历, 和从头开始遍历结果是一样的

既然是链表, 那当然是经典的找到中间节点, 然后从头开始遍历, 只要是相同的话就是回文链表了

哦哦 想错了, 应该是找到中间节点的过程中, 建立 prev 指针, 构建局部的双向链表, 然后遍历的时候取消掉 prev 指针就好了

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const reverseList = (head) => {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

const endOfFirstHalf = (head) => {
    let fast = head;
    let slow = head;
    while (fast.next !== null && fast.next.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

var isPalindrome = function(head) {
    if (head == null) return true;

    // 找到前半部分链表的尾节点并反转后半部分链表
    const firstHalfEnd = endOfFirstHalf(head);
    const secondHalfStart = reverseList(firstHalfEnd.next);

    // 判断是否回文
    let p1 = head;
    let p2 = secondHalfStart;
    let result = true;
    while (result && p2 != null) {
        if (p1.val != p2.val) result = false;
        p1 = p1.next;
        p2 = p2.next;
    }        

    // 还原链表并返回结果
    firstHalfEnd.next = reverseList(secondHalfStart);
    return result;
};

方案二: 递归

后序遍历, 可以做到反向遍历节点

在外部维护一个前序遍历的变量, 做到双向遍历链表节点

let frontPointer;

const recursivelyCheck = (currentNode) => {
    if (currentNode !== null) {
        if (!recursivelyCheck(currentNode.next)) {
            return false;
        }
        if (currentNode.val !== frontPointer.val) {
            return false;
        }
        frontPointer = frontPointer.next;
    }
    return true;
}

var isPalindrome = function(head) {
    frontPointer = head;
    return recursivelyCheck(head);
};